Search for: All records

Abstract We elucidate the relationship between the threshold and the expectation‐threshold of a down‐set. Qualitatively, our main result demonstrates that there exist down‐sets with polynomial gaps between their thresholds and expectation‐thresholds; in particular, the logarithmic gap predictions of Kahn–Kalai and Talagrand (recently proved by Park–Pham and Frankston–Kahn–Narayanan–Park) about up‐sets do not apply to down‐sets. Quantitatively, we show that any collection of graphs on that covers the family of all triangle‐free graphs on satisfies the inequality for some universal , and this is essentially best‐possible. 

Abstract A family of sets is said to be an antichain if for all distinct , and it is said to be a distance‐ code if every pair of distinct elements of has Hamming distance at least . Here, we prove that if is both an antichain and a distance‐ code, then . This result, which is best‐possible up to the implied constant, is a purely combinatorial strengthening of a number of results in Littlewood–Offord theory; for example, our result gives a short combinatorial proof of Hálasz's theorem, while all previously known proofs of this result are Fourier‐analytic. 

Abstract A family of vectors in [ k ] n is said to be intersecting if any two of its elements agree on at least one coordinate. We prove, for fixed k ≥ 3, that the size of any intersecting subfamily of [ k ] n invariant under a transitive group of symmetries is o ( k n ), which is in stark contrast to the case of the Boolean hypercube (where k = 2). Our main contribution addresses limitations of existing technology: while there are now methods, first appearing in work of Ellis and the third author, for using spectral machinery to tackle problems in extremal set theory involving symmetry, this machinery relies crucially on the interplay between up-sets, biased product measures, and threshold behaviour in the Boolean hypercube, features that are notably absent in the problem considered here. To circumvent these barriers, introducing ideas that seem of independent interest, we develop a variant of the sharp threshold machinery that applies at the level of products of posets.